#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <utility>
#include <unordered_map>
#include <map>
#include <algorithm>
#include "student.h"
#include "circle.h"
#include "sort.h"
#include "list.h"
#include "tree.h"

using namespace std;
# define SORT_MAIN	
//# define CIRCLE_MAIN
//# define VEC_MAIN
//# define SLIST_MAIN
//# define TREE_MAIN
//# define DLIST_MAIN
//#define TEMPLATE_MAIN
#define MOD (int)(1e9+7)



class WordDictionary {
public:
	vector<string> dict;
	WordDictionary() {
		dict.clear();
	}

	void addWord(string word) {
		dict.push_back(word);
	}

	bool search(string word) {
		int n = dict.size();
		int n1 = word.size();
		for (int i = 0; i < n; ++i) {
			if (dict[i].size() != n1) { continue; }
			for (int j = 0; j < n1; ++j) {
				if (word[j] == '.') {
					if (j == n1 - 1) {
						return true;
					}
					continue;
				}
				else {
					if (word[j] != dict[i][j]) {
						break;
					}
					if (j == n1 - 1) {
						return true;
					}
				}
			}
		}
		return false;
	}
};



int main(){
#ifdef SORT_MAIN

	int arr[14] = { 6,6,16,9,8,6,5,4,2,5,7,2,2,2 };
	printArray(arr, sizeof(arr) / sizeof(int));
	bubbleSort(arr, sizeof(arr) / sizeof(int));
	selectSort(arr, sizeof(arr) / sizeof(int));
	insertSort(arr, sizeof(arr) / sizeof(int));
	shellSort(arr, sizeof(arr) / sizeof(int));
	printArray(arr, sizeof(arr) / sizeof(int));
	vector<int> nums = { 5,1,1,2,0,0 };
	int n = nums.size();
	quickSort(nums, 0, n - 1);
	mergeSort(nums, 0, n - 1);
	for (auto x : nums)
		cout << x << ' ';
	cout << endl;
#endif
#ifdef CIRCLE_MAIN

	Student A(20162589, "xiyinli", 59);
	Student B(20162588, "son,lee", 98);
	A.print();
	B.print();
#endif
#ifdef VEC_MAIN
	vector<Rect>vec;
	Rect rect;
	rect.id = 1;
	rect.length = 2;
	rect.width = 3;
	vec.push_back(rect);
	vector<Rect>::iterator it = vec.begin();
	cout << (*it).id << " " << endl;
#endif
#ifdef SLIST_MAIN
	CLinkedList a;
	int b1;
	int b2;
	a.topFront();
	a.topBack();
	a.insertAtBack(1);
	a.print();
	a.reverse();
	a.print();
	a.insertAtBack(2);
	a.print();
	a.reverse();
	a.print();
	a.insertAtBack(3);
	a.insertAtBack(4);
	a.print();
	a.reverse();
	a.print();
	a.removeNthFromEnd(-1);
	a.print();
	a.removeNthFromEnd(0);
	a.print();
	a.removeNthFromEnd(2);
	a.print();
	a.removeNthFromEnd(2);
	a.print();
	a.removeNthFromEnd(3);
	a.print();
#endif
#ifdef DLIST_MAIN
	CDlinkedList list;
	list.insertAtFront(34);
	list.insertAtFront(44);
	list.insertAtBack(52);
	list.insertAtBack(22);
	list.printReverse();
	list.insertAfter(22, 33);
	list.insertAfter(52, 100);
	list.print();
	cout << list.topFront() << endl;
	list.print();
	cout << list.topBack() << endl;
	list.print();
	list.remove(100);
	list.printReverse();
	
#endif
#ifdef TREE_MAIN
	CBinTree bst;
	bst.createSampleTree1();
	bst.prettyPrint();
	//bst.preorder();
	bst.inorder();
	//bst.postorder();
	bst.deleteNode(35);
	bst.inorder();
#endif
#ifdef TEMPLATE_MAIN
	cout << "$Template Function!!!$"<< endl;
	int max = max1(20, 25);
	cout << "max = " << max << endl;
	char max_c = max1('z', 'a');
	cout << "max_c = " << max_c << endl;
	float max_f = max1(5.1, 3.0);
	cout << "max_f = " << max_f << endl;

	cout << "$Template Class!!!$" << endl;
	Max<int> int_max(20, 25);
	int imax = int_max.getMaxValue();
	cout << "get int max = " << imax << endl;
	Max<char> char_max('a', 'z');
	char cmax = char_max.getMaxValue();
	cout << "get char max = " << cmax << endl;
	Max<float>float_max(5.1, 3.0);
	float fmax = float_max.getMaxValue();
	cout << "get float max = " << fmax << endl;
#endif
	WordDictionary words;
	words.addWord("bad");
	words.addWord("dad");
	words.addWord("mad");
	bool b1 = words.search("pad");
	bool b2 = words.search("bad");
	bool b3 = words.search(".ad");
	bool b4 = words.search("b..");

	return b2;
}

